#include "stack_queue.h"
#include <map>
#include <stack>
#include <queue>
#include <string>

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
//结点
listNode::listNode(int data_num, listNode *success) {
    data = data_num;
    next = nullptr;
}


//栈
MyStack::MyStack() {
    topNode = nullptr;
    stackSize = 0;
}

MyStack::~MyStack() {
    for(int i = 0; i < stackSize; i ++) {
        listNode *tmp = topNode;
        topNode = topNode->next;
        delete tmp;
    }
}

bool MyStack::push(const int &num) {
    listNode *tmp = new listNode(num);
    tmp->next = topNode;
    topNode = tmp;
    stackSize++;
    return true;
}

bool MyStack::pop(int &item) {
    if(stackSize == 0) {
        return false;
    }
    item = topNode->data;
    listNode *tmp = topNode;
    topNode = topNode->next;
    delete tmp;
    stackSize--;
    return true;
}

bool MyStack::getTop(int &top_num) {
    if(stackSize == 0) {
        return false;
    }
    top_num = topNode->data;
    return true;
}

bool MyStack::getTop(char &top_num) {
    if(stackSize == 0) {
        return false;
    }
    top_num = topNode->data;
    return true;
}
//队列
MyQueue::MyQueue(const int &cap) {
    capacity = cap;
    queue = new int [capacity];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue() {
    capacity = 0;
    front = 0;
    rear = 0;
    delete queue;
}

bool MyQueue::enQueue(const int &num) {
    if((rear + 1) % capacity == front) {
        return false;
    }
    queue[rear] = num;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int &num) {
    if(rear == front) {
        return false;
    }
    num = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int &item) {
    if(rear == front) {
        return false;
    }
    item = queue[front];
    return true;
}

bool MyQueue::isFull() {
    if((rear + 1) % capacity == front) {
        return true;
    }
    return false;
}


//表达式求值
/*int find(char ch[], int length, char c) {
    for(int i = 0; i < length; i ++) {
        if(ch[i] == c) {
            return i;
        }
    }
    return -1;
}

void init_in_stack(char *stack) {

}*/
void init_in_stack(map<char, int> &expression) {
    expression['#'] = 0;
    expression['('] = 1;
    expression['^'] = 2;
    expression['*'] = expression['/'] = expression['%'] = 5;
    expression['+'] = expression['-'] = 3;
    expression[')'] = 8;
}
void init_out_stack(map<char, int> &expression) {
    expression['#'] = 0;
    expression['('] = 8;
    expression['^'] = 6;
    expression['*'] = expression['/'] = expression['%'] = 4;
    expression['+'] = expression['-'] = 2;
    expression[')'] = 1;
}
bool postfixExpression(const string& expression, string &result) {
    stack<char> operation;
    int e_length = expression.length();
    map<char, int> in_stack, out_stack;
    init_in_stack(in_stack);
    init_out_stack(out_stack);

    operation.push('#');
    
    int branket_match = 0;
    bool find_left_branket = false;

    if(e_length == 0) {
        result = "Expression is wrong!";
        return false;
    }
    for(int i = 0; i < e_length; i ++) {
        char ch = expression[i];;
        if(isdigit(ch)) {
            result += ch;
        } else {
            if (ch != '(' && ch != ')' && ch != '+' && ch != '-' && ch != '*' && ch != '/') {
                result = "Expression is wrong!";
                return false; 
            }
            if(ch == ')') {
                branket_match --;
                while(operation.top() != '#' && operation.top() != '(') {
                    result += operation.top();
                    operation.pop();
                }
                if(operation.top() == '(') {
                    find_left_branket = true;
                    operation.pop();
                } else {
                    result = "Expression is wrong!";
                    return false;
                }
                if(!find_left_branket) {
                    result = "Expression is wrong!";
                    return false;
                }
                continue;
            } else {
                if(ch =='(') {
                    branket_match ++;
                    if(i + 1 < e_length) {
                        char next_char = expression[i + 1];
                        if(!isdigit(next_char) && next_char != '(') {
                            result = "Expression is wrong!";
                            return false;
                        }
                    }
                } else {
                    if(i == 0) {
                        result = "Expression is wrong!";
                        return false;
                    }
                    char prev_char = expression[i - 1];
                    if(!isdigit(prev_char) && prev_char != ')') {
                        result = "Expression is wrong!";
                        return false;
                    }
                    if(i + 1 >= e_length) {
                        result = "Expression is wrong!";
                        return false;
                    }
                    char next_char = expression[i + 1];
                    if(!isdigit(next_char) && next_char != '(') {
                        result = "Expression is wrong!";
                        return false;
                    }
                }
                
                
                while(operation.top() != '#') {
                    char op = operation.top();
                    if(in_stack[op] > out_stack[ch]) {
                        result += op;
                        operation.pop();
                    } else {
                        break;
                    }
                }
                operation.push(ch);
            }
        }
    }
    if(branket_match != 0) {
        result = "Expression is wrong!";
        return false;
    }
    while(operation.top() != '#') {
        if(operation.top() == '(') {
            result = "Expression is wrong!";
            return false;
        }
        result += operation.top();
        operation.pop();
    }

    operation.pop();
    return true;
}

bool calculate(int dig1, int dig2, char op, int &result) {
    if(op == '+') {
        result = dig1 + dig2;
    } else if(op == '-') {
        result = dig1 - dig2;
    } else if(op == '*') {
        result = dig1 * dig2;
    } else if (op == '/') {
        if(dig2 == 0) {
            return false;
        }
        result = dig1 / dig2;
    } else if (op == '%') {
        if(dig2 == 0) {
            return false;
        }
        result = dig1 % dig2;
    } else if(op == '^') {
        result = 1;
        for(int i = 0; i < dig2; i ++) {
            result *= dig1;
        }
    }
    return true;
}

bool expressionVal(const string &expression, int &result) {
    string post_expression;
    postfixExpression(expression, post_expression);
    stack<int> digit;
    int tmp = 0;
    int p_length = post_expression.length();
    for(int i = 0; i < p_length; i ++) {
        char ch = post_expression[i];
        if(isdigit(ch)) {
            digit.push(ch - '0');
        } else {
            int d1, d2;
            if(!digit.empty()) {
                d1 = digit.top();
                digit.pop();
            } else {
                result = 0;
                return false;
            }

            if(!digit.empty()) {
                d2 = digit.top();
                digit.pop();
            } else {
                result = 0;
                return false;
            }

            calculate(d2, d1, ch, tmp);
            digit.push(tmp);
        }
    }
    if(digit.size() != 1) {
        result = 0;
        return false;
    }
    result = digit.top();
    return true;
}

void yanghui(const int &row) {
    queue<int> num;
    int s = 0;
    num.push(1);
    num.push(1);
    for(int i = 1; i <= row; i ++) {
        cout << endl;
        num.push(0);
        for(int j = 1; j <= i + 2; j ++) {
            int t = num.front();
            num.pop();
            num.push(s + t);
            s = t;
            if(j != i + 2) {
                cout << s << " ";
            }
        }
    }
}





